/**
 * @author 徐楠
 * @date 2022/4/28 16:54
 * @version 1.0
 */

package com.xunan.likou;

import java.util.ArrayList;
import java.util.List;

public class CountBinarySubstring {
    public static void main(String[] args) {
        int i = countBinarySubstrings("00110011");
        System.out.println(i);
    }

    /**
     * 思路与算法
     *
     * 我们可以将字符串 ss 按照 0 和 1 的连续段分组，存在 list 数组中，
     * 例如 s = 00111011 ，可以得到这样的 list 数组：list ={2,3,1,2}。
     *
     * 这里 list 数组中两个相邻的数一定代表的是两种不同的字符。
     * 假设 list 数组中两个相邻的数字为 u 或者 v，它们对应着 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。
     * 它们能组成的满足条件的子串数目为 min{u,v}，即一对相邻的数字对答案的贡献。
     *
     * 我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。
     *
     * @param s
     * @return
     */
    public static int countBinarySubstrings(String s) {
        List<Integer> list = new ArrayList<>();
        char c = s.charAt(0);
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                count++;
            } else {
                c = s.charAt(i);
                System.out.println("index " + i);
                list.add(count);
                count = 1;
            }
        }
        //添加最后一次
        list.add(count);
        System.out.println(list);
        int answer = 0;
        for (int i = 1; i < list.size(); ++i) {
            answer += Math.min(list.get(i), list.get(i - 1));
        }
        return answer;
    }

    public int countBinarySubstringsPlus(String s) {
        List<Integer> counts = new ArrayList<>();
        int ptr = 0, n = s.length();
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            counts.add(count);
        }
        int ans = 0;
        for (int i = 1; i < counts.size(); ++i) {
            ans += Math.min(counts.get(i), counts.get(i - 1));
        }
        return ans;
    }

}
